<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Sort</title>
</head>
<body>
<script>
  const arr1 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr2 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr3 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr4 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr5 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr6 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr7 = [9, 1, 29, 23, 16, 34, 25, 112, 14]
  const arr8 = [9, 1, 29, 23, 16, 34, 25, 112, 14]

  // 冒泡排序
  function bubbleSort(arr) {
    if (arr.length <= 1) return arr
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
      }
    }
    return arr
  }

  // 高级冒泡排序
  function seniorBubbleSort(arr) {
    if (arr.length <= 1) return arr
    let boundary = arr.length - 1
    let lastIndex = 0
    for (let i = 0; i < arr.length; i++) {
      let mark = true
      for (let j = 0; j < boundary; j++) {
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
          lastIndex = j
          mark = false
        }
      }
      boundary = lastIndex
      if (mark) break
    }
    return arr
  }

  // 选择排序
  function selectionSort(arr) {
    if (arr.length <= 1) return arr
    let minIndex
    for (let i = 0; i < arr.length - 1; i++) {
      minIndex = i
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j
        }
      }
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
    return arr
  }

  // 插入排序
  function insertionSort(arr) {
    if (arr.length <= 1) return arr
    let current
    for (let i = 0; i < arr.length - 1; i++) {
      current = arr[i + 1]
      let preIndex = i
      while (preIndex >= 0 && current < arr[preIndex]) {
        arr[preIndex + 1] = arr[preIndex]
        preIndex--
      }
      arr[preIndex + 1] = current
    }
    return arr
  }

  // 希尔排序
  function shellSort(arr) {
    for (let gap = arr.length / 2; gap >= 1; gap = Math.floor(gap / 2)) {
      for (let i = gap; i < arr.length; i++) {
        for (let j = i; j >= gap && arr[j] < arr[j - gap]; j = j - gap) {
          [arr[j - gap], arr[j]] = [arr[j], arr[j - gap]]
        }
      }
    }
    return arr
  }

  // 优化希尔排序
  function opShellSort(arr) {
    let gap = 1
    while (gap < arr.length / 3) {
      gap = gap * 3 + 1
    }
    for (gap; gap >= 1; gap = Math.floor(gap / 3)) {
      for (let i = gap; i < arr.length; i++) {
        for (let j = i; j >= gap && arr[j] < arr[j - gap]; j = j - gap) {
          [arr[j - gap], arr[j]] = [arr[j], arr[j - gap]]
        }
      }
    }
    return arr
  }

  // 归并排序
  function mergeSort(arr) {
    const merge = (left, right) => {
      const result = []
      let i = 0, j = 0
      while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
          result.push(left[i++])
        } else {
          result.push(right[j++])
        }
      }
      while (i < left.length) {
        result.push(left[i++])
      }
      while (j < right.length) {
        result.push(right[j++])
      }
      return result
    }
    const sort = arr => {
      if (arr.length <= 1) return arr
      const mid = Math.floor(arr.length / 2)
      const left = arr.slice(0, mid)
      const right = arr.slice(mid)
      return merge(mergeSort(left), mergeSort(right))
    }
    return sort(arr)
  }

  // 快速排序
  function quickSort(arr) {
    if (arr.length <= 1) return arr
    const list = [...arr]
    const pivot = list[Math.floor(list.length / 2)]
    const left = list.filter(item => item < pivot)
    const right = list.filter(item => item > pivot)
    return [...quickSort(left), pivot, ...quickSort(right)]
  }

  const bubbleResult = bubbleSort(arr1)
  const seniorBubbleResult = seniorBubbleSort(arr2)
  const selectionResult = selectionSort(arr3)
  const insertionResult = insertionSort(arr4)
  const shellResult = shellSort(arr5)
  const opShellResult = opShellSort(arr6)
  const mergeResult = mergeSort(arr7)
  const quickResult = quickSort(arr8)
  console.log(bubbleResult)
  console.log(seniorBubbleResult)
  console.log(selectionResult)
  console.log(insertionResult)
  console.log(shellResult)
  console.log(opShellResult)
  console.log(mergeResult)
  console.log(quickResult)
</script>
</body>
</html>
